package com.hard;

//https://leetcode.cn/problems/sudoku-solver/solutions/5656/hui-su-fa-jie-shu-du-by-i_use_python/
class Solution37 {
    boolean[][] rowd = new boolean[9][10];
    boolean[][] cold = new boolean[9][10];
    boolean[][][] matd = new boolean[3][3][10];

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] >= '1' && board[i][j] <= '9') {
                    int num = board[i][j] - '0';
                    rowd[i][num] = true;
                    cold[j][num] = true;
                    matd[i / 3][j / 3][num] = true;
                }
            }
        }
        back(0, 0, board);
    }

    public boolean back(int row, int col, char[][] board) {
        if (col == board[0].length) {
            col = 0;
            row++;
            if (row == board.length) return true;
        }
        if (board[row][col] == '.') {
            for (int i = 1; i < 10; i++) {
                boolean flag = !(rowd[row][i] || cold[col][i] || matd[row / 3][col / 3][i]);
                if (flag) {
                    rowd[row][i] = true;
                    cold[col][i] = true;
                    matd[row / 3][col / 3][i] = true;
                    board[row][col] = (char) (i + '0');
                    if (back(row, col + 1, board)) return true;
                    board[row][col] = '.';
                    rowd[row][i] = false;
                    cold[col][i] = false;
                    matd[row / 3][col / 3][i] = false;
                }
            }
        } else return back(row, col + 1, board);
        return false;
    }
}